RSA 暗号
用語
漢字が潰れて錠と鍵の違いが一瞬見分けられないので絵文字を追加する
漢字が潰れて～
アルゴリズム
受信側
1. 大きな素数$ p,$ qを生成、$ n=pqとする
$ nから$ p,$ qを求めるのは難しい
2. $ (p-1)(q-1)と互いに素な整数$ lを取ってくる 3. $ lk \equiv 1\ {\rm mod}\ (p-1)(q-1)となる$ kを取ってくる
4.
送信側
1. 送りたいメッセージ$ mは$ n未満の正の整数とする
2. 公開錠🔓$ lを用いて暗号文$ C=m^{l}\ {\rm mod}\ n を計算して送る 受信側
$ m=C^{k}\ {\rm mod}\ nが成立するので秘密鍵🔑$ kを用いて複合できる 補足
暗号文$ Cと公開錠🔓$ n,$ lから$ mを復元することは難しいと信じられている 今まで無数の攻撃が加えられ、破られていない実績があるので信じられている
小さい数での例
受信側
1. 素数$ p:=7,$ q:=13を生成、$ n=pq:=91とする
2. $ (p-1)(q-1)=6\times12=72と互いに素な整数$ l:=67を取ってくる 3. $ lk \equiv 1\ {\rm mod}\ (p-1)(q-1)となる$ kを取ってくる
$ k=67^{\rm 70}\ {\rm mod}\ 72=43
4.
$ n=91と$ l=67を公開する (公開錠🔓) 送信側
1. 送りたいメッセージ$ m=63は$ n=91未満の正の整数とする
2. 公開錠🔓を用いて暗号文$ C=m^{l}\ {\rm mod}\ n=63^{67}\ {\rm mod}\ 91=28 を計算して送る 受信側
$ m=C^{k}\ {\rm mod}\ n=28^{43}\ {\rm mod}\ 91=63が成立するので複合できる
やってみた体感
$ p,$ q,$ lは自由に選べるのだが、適切な物を選ばないと周期が短くなって攻撃が容易になる可能性がある
多分他の条件もついているはず
周期の短さで候補を絞れないように選ぶことはできるか？
つまり周期を最大の $ nとか$ (p-1)(q-1)にできないか？
できない場合、周期の中から平文っぽい物を探す攻撃方法が使えてしまう。
「平文っぽさ」をどう計算するかは別の問題になるが
ホントか？周期は鍵長の指数オーダーぐらいになるぞ
そこそこ大きめの周期になるように選んでおけば心配はいらないのでは
$ l=(p-1)(q-1)-1にすると取り敢えず$ (p-1)(q-1)と互いに素にすることはできるが、$ k=lになってしまい、公開鍵と秘密鍵が一致してバレる間抜けになる
実際は平文に乱数をくっつけたものを暗号化する
同じ平文を暗号化したものがあれば暗号解読のヒントになるため
小さい$ mに対しては容易に解読できてしまうため
証明1
$ lk \equiv 1\ {\rm mod}\ (p-1)(q-1)となる$ kを取ってこれることの証明
$ lは$ (p-1)(q-1)と互いに素になるように決めたので、 $ 1\equiv l^{(p-1)(q-1)-1}\mod (p-1)(q-1)
$ \equiv l\times l^{(p-1)(q-1)-2}\mod (p-1)(q-1)
$ \therefore k=l^{(p-1)(q-1)-2}\ {\rm mod}\ (p-1)(q-1)とすればよい
なお、$ lk \equiv 1\ {\rm mod}\ (p-1)(q-1)となる$ kは一意に定まる
$ lと$ (p-1)(q-1)が互いに素なため、
$ 0,l,2l,3l,\cdots,\{(p-1)(q-1)-1\}lを$ (p-1)(q-1)で割ったあまりはすべて異なるため
証明2
$ m=C^{k}\ {\rm mod}\ nが成立するので秘密鍵🔑$ kを用いて複合できることの証明 $ C=m^l\ {\rm mod}\ nなので、$ m\equiv m^{lk}\ {\rm mod}\ n を示す
$ n=pqより$ m\equiv m^{lk}\ {\rm mod}\ pを示せばよい
$ qについては対称性から同様のことが言える
$ m\equiv 0\ {\rm mod}\ pのとき:$ m\equiv m^{lk}\ {\rm mod}\ nは言える
$ m\not\equiv 0\ {\rm mod}\ pのとき:
$ lk \equiv 1\ {\rm mod}\ (p-1)(q-1)となるようにしているので
$ lk=1+(p-1)N
$ m^{lk}\equiv m\cdot(m^{p-1})^N\equiv m \mod p
気になる
P=NP 問題が肯定的に解決されると RSA が素早く解読されてマズイみたいな言説があるが、問題はそこじゃない 逆に P=NP 問題が肯定的に解決されたとしても、アルゴリズムの存在のみが示されて、構成法が分からない可能性もある アルゴリズムが構成できたとしても多項式の指数がデカすぎるとソレはソレで RSA 暗号は危険にさらされない